package com.scott.ch400.atguigu.ch100.v01;

/**
 * @author 黄后林
 * @date 2022-08-11 08:27:19
 * @note 二分法  前提：有序
 */
public class BinarySearchV01 {

    public static void main(String[] args) {

        int[] arr={1,8,10,89,1000,1234};
        int findVal =1000;
        int index = binarySearch(arr, 0, arr.length - 1, findVal);
        System.out.println(index);
    }


    /**
     * 方法描述:  二分查找的递归实现
     * @author: 黄后林
     * @date: 2022/8/11 8:32
     * @param array      在哪个数组中查找
     * @param left       下标开始位置
     * @param right      下标结束位置
     * @param findVal    要查找的数
     * @return int       下标
     */
    public static int binarySearch(int[] array,int left,int right,int findVal){


        //1 什么时候结束递归
        if(left>right){
            return -1;
        }

        //2 做正常的业务


        int mid =(left + right)/2;
        int midVal = array[mid];

        if(findVal > midVal){
            // 向右边继续找=向右递归
            left=mid+1;
            return binarySearch(array,left,right,findVal);
        }else if(findVal<midVal){
            // 向左边继续找=向左递归
            right=mid-1;
            return binarySearch(array,left,right,findVal);
        }else{
            return mid;
        }

    }


}
